home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part2 / 13475 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  2.7 KB
  1. Path: newshub.ccs.yorku.ca!news
  2. From: "Shahed A. Quazi" <yu106781@yorku.ca>
  3. Newsgroups: comp.lang.c
  4. Subject: PlLS HELP with my "SUCCESSOR" and "REMOVE" function !!
  5. Date: Sun, 07 Apr 1996 01:22:55 -0800
  6. Organization: York University, Canada
  7. Message-ID: <3167896F.31D9@yorku.ca>
  8. NNTP-Posting-Host: pugsly13.slip.yorku.ca
  9. Mime-Version: 1.0
  10. Content-Type: text/plain; charset=us-ascii
  11. Content-Transfer-Encoding: 7bit
  12. X-Mailer: Mozilla 2.0 (Win16; I)
  13.  
  14. Hi,
  15. The following are the two functions I wrote, for a B-TREE program,
  16. where the user should be able to insert, search and delete key from
  17. the tree. 
  18.  
  19. Now, my problem is, the deletion is not working and I would really 
  20. appreciate if someone could tell me what am I doing wrong in the 
  21. following two functions.
  22.  
  23. ....  
  24. typedef struct {
  25.     short keycount;            /* number of keys in page       */
  26.     int  key[MAXKEYS];         /* the actual keys              */
  27.     short child[MAXKEYS+1];    /* ptrs to RRNs of descendants  */
  28. } BTPAGE;
  29. ..............
  30. ....................
  31.  
  32. /*===============================================================*
  33.   This function replaces the key "page.key[pos]" with its
  34.   immediate successor in the B-TREE, and then returns RRN (Relative     
  35. Record Number)of the duplicate of this successor residing in the leaf
  36.   page. 
  37. *==============================================================*/
  38. short SUCCESSOR (short found_rrn, short pos)
  39. {
  40.    short rrn_succ;
  41.    BTPAGE page;
  42.    BTPAGE ch_page;
  43.  
  44.    btread (found_rrn, &page);
  45.    rrn_succ = page.child[pos];
  46.  
  47.    while ((btread(rrn_succ, &ch_page)) && (ch_page.child[0]!= NIL))
  48.  
  49.           rrn_succ = ch_page.child[0];
  50.  
  51.  
  52.    btread (rrn_succ, &ch_page);     /*read the page containing */
  53.                                     /* immediate successor.    */
  54.    if (ch_page.keycount <= MINKEYS) /* if successor page has   */
  55.    return (-1);                     /* less then MIN keys, then*/
  56.    else{                            /* return -1.              */
  57.    page.key[pos] = ch_page.key[1];
  58.  
  59.    btwrite(found_rrn, &page);  /*writes back to the disk.*/
  60.  
  61.    return (rrn_succ);}             /*otherwise, swap the key   */
  62. }  /*end function */               /* with successor.          */
  63.  
  64. /*==============================================================*
  65.   Delets the key from a leaf page .
  66.   Here "page" contains the key, "rrn_page" is RRN of this page
  67.   and "pos" is the position of the key.     
  68.  *=============================================================*/
  69. void REMOVE_KEY(BTPAGE page, short rrn_page, short pos){
  70.  
  71.    short i;
  72.    for (i = pos+1; i <= page.keycount; i++)
  73.       page.key[i-1] = page.key[i];
  74.  
  75.    (page.keycount)--;
  76.    btwrite(rrn_page, &page);  /* write back the page to disk. */
  77. } /* end function */
  78.  
  79.  
  80. thanks in advance,
  81. shahed
  82.